Search Results

Documents authored by Merkle, Wolfgang

Document
DOI: 10.4230/LIPIcs.STACS.2012.172
Constant compression and random weights

Authors: Wolfgang Merkle and Jason Teutsch

Published in: LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)

Abstract
Omega numbers, as considered in algorithmic randomness, are by definition real numbers that are equal to the halting probability of a universal prefix-free Turing machine. Omega numbers are obviously left-r.e., i.e., are effectively approximable from below. Furthermore, among all left-r.e. real numbers in the appropriate range between 0 and 1, the Omega numbers admit well-known characterizations as the ones that are Martin-Löf random, as well as the ones such that any of their effective approximation from below is slower than any other effective approximation from below to any other real, up to a constant factor. In what follows, we obtain a further characterization of Omega numbers in terms of Theta numbers. Tadaki considered for a given prefix-free Turing machine and some natural number a the set of all strings that are compressed by this machine by at least a bits relative to their length, and he introduced Theta numbers as the weight of sets of this form. He showed that in the case of a universal prefix-free Turing machine any Theta number is an Omega number and he asked whether this implication can be reversed. We answer his question in the affirmative and thus obtain a new characterization of Omega numbers. In addition to the one-sided case of the set of all strings compressible by at least a certain number a of bits, we consider sets that comprise all strings that are compressible by at least a but no more than b bits, and we call the weight of such a set a two-sided Theta number. We demonstrate that in the case of a universal prefix-free Turing machine, for given a and all sufficiently large b the corresponding two-sided Theta number is again an Omega number. Conversely, any Omega number can be realized as two-sided Theta number for any pair of natural numbers a and b>a.
Cite as

Wolfgang Merkle and Jason Teutsch. Constant compression and random weights. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 172-181, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{merkle_et_al:LIPIcs.STACS.2012.172,
  author =	{Merkle, Wolfgang and Teutsch, Jason},
  title =	{{Constant compression and random weights}},
  booktitle =	{29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
  pages =	{172--181},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-35-4},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{14},
  editor =	{D\"{u}rr, Christoph and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.172},
  URN =		{urn:nbn:de:0030-drops-34351},
  doi =		{10.4230/LIPIcs.STACS.2012.172},
  annote =	{Keywords: computational complexity, Kolmogorov complexity, algorithmic randomness, Omega number}
}
Document
DOI: 10.4230/LIPIcs.STACS.2011.452
Solovay functions and K-triviality

Authors: Laurent Bienvenu, Wolfgang Merkle, and Andre Nies

Published in: LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)

Abstract
As part of his groundbreaking work on algorithmic randomness, Solovay demonstrated in the 1970s the remarkable fact that there are computable upper bounds of prefix-free Kolmogorov complexity $K$ that are tight on infinitely many values (up to an additive constant). Such computable upper bounds are called Solovay functions. Recent work of Bienvenu and Downey~[STACS 2009, LIPIcs 3, pp 147-158] indicates that Solovay functions are deeply connected with central concepts of algorithmic randomness such as $Omega$ numbers, K-triviality, and Martin-Loef randomness. In what follows, among other results we answer two open problems posed by Bienvenu and Downey about the definition of $K$-triviality and about the Gacs-Miller-Yu characterization of Martin-Loef randomness. The former defines a sequence A to be K-trivial if K(A|n) <=^+ K(n), the latter asserts that a sequence A is Martin-Loef random iff C(A|n) >=^+ n-K(n). So both involve the noncomputable function K. As our main results we show that in both cases K(n) can be equivalently replaced by any Solovay function, and, what is more, that among all computable functions such a replacement is possible exactly for the Solovay functions. Moreover, similar statements hold for the larger class of all right-c.e. in place of the computable functions. These full characterizations, besides having significant theoretical interest on their own, will be useful as tools when working with K-trivial and Martin-Loef random sequences.
Cite as

Laurent Bienvenu, Wolfgang Merkle, and Andre Nies. Solovay functions and K-triviality. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 452-463, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{bienvenu_et_al:LIPIcs.STACS.2011.452,
  author =	{Bienvenu, Laurent and Merkle, Wolfgang and Nies, Andre},
  title =	{{Solovay functions and K-triviality}},
  booktitle =	{28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)},
  pages =	{452--463},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-25-5},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{9},
  editor =	{Schwentick, Thomas and D\"{u}rr, Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.452},
  URN =		{urn:nbn:de:0030-drops-30345},
  doi =		{10.4230/LIPIcs.STACS.2011.452},
  annote =	{Keywords: Algorithmic randomness, Kolmogorov complexity, K-triviality}
}
Document
DOI: 10.4230/OASIcs.CCA.2009.2260
Separations of Non-monotonic Randomness Notions

Authors: Laurent Bienvenu, Rupert Hölzl, Thorsten Kräling, and Wolfgang Merkle

Published in: OASIcs, Volume 11, 6th International Conference on Computability and Complexity in Analysis (CCA'09) (2009)

Abstract
In the theory of algorithmic randomness, several notions of random sequence are defined via a game-theoretic approach, and the notions that received most attention are perhaps Martin-L\"of randomness and computable randomness. The latter notion was introduced by Schnorr and is rather natural: an infinite binary sequence is computably random if no total computable strategy succeeds on it by betting on bits in order. However, computably random sequences can have properties that one may consider to be incompatible with being random, in particular, there are computably random sequences that are highly compressible. The concept of Martin-L\"of randomness is much better behaved in this and other respects, on the other hand its definition in terms of martingales is considerably less natural. Muchnik, elaborating on ideas of Kolmogorov and Loveland, refined Schnorr's model by also allowing non-monotonic strategies, i.e.\ strategies that do not bet on bits in order. The subsequent ``non-monotonic'' notion of randomness, now called Kolmogorov-Loveland-randomness, has been shown to be quite close to Martin-L\"of randomness, but whether these two classes coincide remains a fundamental open question. In order to get a better understanding of non-monotonic randomness notions, Miller and Nies introduced some interesting intermediate concepts, where one only allows non-adaptive strategies, i.e., strategies that can still bet non-monotonically, but such that the sequence of betting positions is known in advance (and computable). Recently, these notions were shown by Kastermans and Lempp to differ from Martin-L\"of randomness. We continue the study of the non-monotonic randomness notions introduced by Miller and Nies and obtain results about the Kolmogorov complexities of initial segments that may and may not occur for such sequences, where these results then imply a complete classification of these randomness notions by order of strength.
Cite as

Laurent Bienvenu, Rupert Hölzl, Thorsten Kräling, and Wolfgang Merkle. Separations of Non-monotonic Randomness Notions. In 6th International Conference on Computability and Complexity in Analysis (CCA'09). Open Access Series in Informatics (OASIcs), Volume 11, pp. 71-82, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{bienvenu_et_al:OASIcs.CCA.2009.2260,
  author =	{Bienvenu, Laurent and H\"{o}lzl, Rupert and Kr\"{a}ling, Thorsten and Merkle, Wolfgang},
  title =	{{Separations of Non-monotonic Randomness Notions}},
  booktitle =	{6th International Conference on Computability and Complexity in Analysis (CCA'09)},
  pages =	{71--82},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-12-5},
  ISSN =	{2190-6807},
  year =	{2009},
  volume =	{11},
  editor =	{Bauer, Andrej and Hertling, Peter and Ko, Ker-I},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.CCA.2009.2260},
  URN =		{urn:nbn:de:0030-drops-22601},
  doi =		{10.4230/OASIcs.CCA.2009.2260},
  annote =	{Keywords: Martin-L\"{o}f randomness, Kolmogorov-Loveland randomness, Kolmogorov complexity, martingales, betting strategies}
}
Document
DOI: 10.4230/DagSemProc.06051.1
06051 Abstracts Collection – Kolmogorov Complexity and Applications

Authors: Marcus Hutter, Wolfgang Merkle, and Paul M.B. Vitanyi

Published in: Dagstuhl Seminar Proceedings, Volume 6051, Kolmogorov Complexity and Applications (2006)

Abstract
From 29.01.06 to 03.02.06, the Dagstuhl Seminar 06051 ``Kolmogorov Complexity and Applications'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Marcus Hutter, Wolfgang Merkle, and Paul M.B. Vitanyi. 06051 Abstracts Collection – Kolmogorov Complexity and Applications. In Kolmogorov Complexity and Applications. Dagstuhl Seminar Proceedings, Volume 6051, pp. 1-17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{hutter_et_al:DagSemProc.06051.1,
  author =	{Hutter, Marcus and Merkle, Wolfgang and Vitanyi, Paul M.B.},
  title =	{{06051 Abstracts Collection – Kolmogorov Complexity and Applications}},
  booktitle =	{Kolmogorov Complexity and Applications},
  pages =	{1--17},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6051},
  editor =	{Marcus Hutter and Wolfgang Merkle and Paul M.B. Vitanyi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06051.1},
  URN =		{urn:nbn:de:0030-drops-6632},
  doi =		{10.4230/DagSemProc.06051.1},
  annote =	{Keywords: Information theory, Kolmogorov Complexity, effective randomnes, algorithmic probability, recursion theory, computational complexity, machine learning knowledge discovery}
}
Document
DOI: 10.4230/DagSemRep.377
Centennial Seminar on Kolmogorov Complexity and Applications (Dagstuhl Seminar 03181)

Authors: Bruno Durand, Leonid A. Levin, Wolfgang Merkle, Alexander Shen, and Paul M. B. Vitanyi

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Bruno Durand, Leonid A. Levin, Wolfgang Merkle, Alexander Shen, and Paul M. B. Vitanyi. Centennial Seminar on Kolmogorov Complexity and Applications (Dagstuhl Seminar 03181). Dagstuhl Seminar Report 377, pp. 1-6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2003)

Copy BibTex To Clipboard

@TechReport{durand_et_al:DagSemRep.377,
  author =	{Durand, Bruno and Levin, Leonid A. and Merkle, Wolfgang and Shen, Alexander and Vitanyi, Paul M. B.},
  title =	{{Centennial Seminar on Kolmogorov Complexity and Applications (Dagstuhl Seminar 03181)}},
  pages =	{1--6},
  ISSN =	{1619-0203},
  year =	{2003},
  type = 	{Dagstuhl Seminar Report},
  number =	{377},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.377},
  URN =		{urn:nbn:de:0030-drops-152578},
  doi =		{10.4230/DagSemRep.377},
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact